1. Field of the Invention
The present invention generally relates to datarace detection for multithreaded object-oriented programs. More particularly, this invention provides a unique combination of static datarace analysis, optimized instrumentation, runtime access caching and runtime detection phases.
2. Description of the Related Art
A datarace occurs in a multithreaded program when two threads access the same memory location with no ordering constraints enforced between the accesses, such that at least one of the accesses is a write. In most cases, a datarace is a programming error. Furthermore, programs containing dataraces are notoriously difficult to debug because they can exhibit different functional behaviors even when executed repeatedly with the same set of inputs and the same execution order of synchronization operations. Because of the detrimental effects of dataraces on the reliability and comprehensibility of multithreaded software, it is widely recognized that tools for automatic detection of dataraces can be extremely valuable. As a result, there has been a substantial amount of past work in building tools for analysis and detection of dataraces.
Most previous dynamic datarace detection techniques have been relatively precise, in that most races reported correspond to truly unsynchronized accesses to shared memory. However, these detectors incur order-of-magnitude overheads in the range of 3 times to 30 times. Recent approaches reduce the overhead of datarace detection, but at the cost of decreased precision. For example, monitoring dataraces at the object level rather than the memory-location level reduced overheads for datarace detection to the range of 16% to 129% but resulted in many spurious race reports.
Past research on datarace detection can be classified as ahead-of-time, on-the-fly, or post-mortem. These approaches offer different trade-offs along ease-of-use, precision, efficiency, and coverage dimensions.
Ahead-of-time datarace detection is usually performed in static datarace analysis tools which yield high coverage by considering the space of all possible program executions and identifying dataraces that might occur in any one of them. Flanagan and Freund's datarace detection tool is a static tool for Java (C. Flanagan and S. N. Freund. Type-based race detection for java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 219-232, June 2000) based on type-based equivalence of lock variables. Guava is a dialect of Java that statically disallows dataraces by preventing concurrent accesses to shared data (D. F. Bacon, R. E. Strom, and A. Tarafdar. Guava: A dialect of java without data races. In ACM Conference on Object Oriented Programming Systems, Languages, and Applications, 2000). Only instances of classes belonging to the class category called monitor can be shared by multiple threads. By serializing all accesses to fields or methods of the same shared data, Guava can prevent dataraces. Boyapati and Rinard propose a system of type annotations for Java that ensures a well-typed program is datarace-free and allows the programmer to write a generic class and subclass it with different protection mechanisms (C. Boyapati and M. Rinard. A parameterized type system for race-free java programs. In ACM Conference on Object-Oriented Programming Systems, Languages, and Application, 2001).
Warlock is an annotation-based static datarace detection tool for ANSI C programs (N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97-106, 1993), which also supports lock-based synchronization. Aiken and Gay's work statically detects dataraces in SPMD programs (A. Aiken and D. Gay. Barrier interference. In Proceedings of the 25th Symposium on Principles of Programming Languages (POPL), pages 342-354, January 1998). Since SPMD programs employ barrier-style synchronizations, they need not track locks held at each statement.
The key advantage of dynamic analysis approaches such as on-the-fly and post-mortem datarace detection is the precision of the results (few or no false positives), but in past work this advantage usually came at a high cost in efficiency. A dynamic approach also has more limited coverage than a static approach because it only reports dataraces observed in a single dynamic execution. In some cases, dynamic tools can improve coverage by considering alternate orderings of synchronization operations that are consistent with the actual events observed in the original program execution (S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4): 391-411, 1997).
Dinning and Schonberg introduced the idea of detecting dataraces based on a proper locking discipline. Their system employed a detection approach based on both the happened-before relation and lock sets, which they called “lock covers.” Their subtraction optimization uses a notion similar to the weaker-than relation described below, but they only suggest using the optimization in the detector itself.
Eraser's datarace detection algorithm is based on lock-based synchronization (S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4): 391-411, 1997). Eraser enforces the constraint that each shared memory location is protected by a unique lock throughout an execution. Eraser works independently of the input source language by instrumenting binary code, but its runtime overhead is in the range of 10 times to 30 times.
Praun and Gross's object race detection (C. v. Praun and T. Gross. Object race detection. In ACM conference on Object-Oriented Programming Systems, Languages, and Application, 2001) greatly improves on Eraser's performance by applying escape analysis to filter out non-datarace statements and by detecting dataraces at the object level instead of at the level of each memory location (their overhead ranges from 16% to 129% on the same benchmarks the inventors used, with less than 25% space overhead). However, their coarser granularity of datarace detection (which includes treating a method call on an object as a write) leads to the reporting of many dataraces which are not true dataraces i.e., the reported races do not indicate unordered concurrent accesses to shared state.
TRaDe is similar to object race detection in that they both apply escape analysis (M. Christianens and K. De Bosschere. TraDE, a topological approach to on-the-fly race detection in java programs. Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01), April 2001), although TRaDe does the analysis dynamically. TraDe's datarace detection is based on the happens-before relation. TRaDe adds a runtime overhead ranging from 4 times to 15 times (M. Christianens and K. De Bosschere. TraDE, a topological approach to on-the-fly race detection in java programs. Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01), April 2001) compared to an interpreter, with approximately 3 times space overhead.
AssureJ (Kuck & Associates, Inc., 1906 Fox Drive, champaign, IL 61820-7345, USA. AsureJ User's Manual, 2.0 edition, March 1999) and JProbe (KL Group, 260 King Street East, Toronto, Ontario, Canada. Getting Started with JProbe.) are commercial products that can dynamically detect dataraces in Java programs. AssureJ has been observed to have overhead ranging from 3 times to 30 times, while JProbe's memory requirements make its use practically impossible for any reasonably sized program.
Min and Choi's hardware-based scheme uses the cache coherence protocol, and Richards and Larus' work uses the Distributed Shared-Memory (DSM) computer's memory coherence protocol, respectively, in collecting information for on-the-fly datarace detection.
Most dynamic datarace detection techniques for SPMD programs work either as post-mortem tools or as on-the-fly tools, by collecting information from actual executions with software instrumentation. A post-mortem approach offers the possibility of improving on-line efficiency (by moving the bulk of the work to the post-mortem phase) at the cost of complicating ease-of-use. However, the size of the trace structure can grow prohibitively large thus making the post-mortem approach infeasible for long-running programs.
Another dimension that can be used to classify past work on datarace detection is the underlying concurrency model. Past work on datarace detection was historically targeted to multithreaded programs. However, those results are not applicable to the object-based concurrency models present in multithreaded object-oriented programming languages such as Java.
Netzer and Miller categorize dynamic dataraces into actual, apparent, and feasible dataraces (R. H. Netzer and B. P. Miller. What are race conditions? Some issues and formalizations. ACM Letters on Programming Languages and Systems, 1(1): 74-88, march 1992.). Choi and Min describe how to identify and reproduce the race frontier, which is the set of dataraces not affected by any other dataraces. By repeatedly reproducing and correcting the dataraces in the race frontier, one can identify all the dataraces that occur in executions.
Thus, past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3 times to 30 times.